#include <vector>
#include <limits.h>
#include <algorithm>
using namespace std;

void dijkstra(int N, int start, int** roadlength, int** flow, int** restrictions, int* distance, int* previous, bool* visited) {
    for (int i = 0; i < N; i++) {
        distance[i] = roadlength[start][i];
        visited[i] = false;
        previous[i] = (distance[i] < INT_MAX && i != start) ? start : -1;
    }
    distance[start] = 0;
    visited[start] = true;

    for (int i = 0; i < N - 1; i++) {
        int min_distance = INT_MAX;
        int stop = start;
        for (int j = 0; j < N; j++) {
            if (!visited[j] && distance[j] < min_distance) {
                min_distance = distance[j];
                stop = j;
            }
        }
        visited[stop] = true;
        for (int k = 0; k < N; k++) {
            if (!visited[k] && roadlength[stop][k] < INT_MAX && flow[stop][k] < restrictions[stop][k] &&
                distance[stop] + roadlength[stop][k] < distance[k]) {
                distance[k] = distance[stop] + roadlength[stop][k];
                previous[k] = stop;
            }
        }
    }
}

vector<int> buildPath(int start, int end, int* previous) {
    vector<int> path;
    int node = end;
    while (node != -1) {
        path.push_back(node);
        node = previous[node];
    }
    reverse(path.begin(), path.end());
    return path;
}

#include <queue>
using namespace std;

vector<vector<int>> yensAlgorithm(int N, int start, int end, int** roadlength, int** flow, int** restrictions, int K) {
    vector<vector<int>> paths;
    if (start == end) {
        paths.push_back(vector<int>{start});
        return paths;
    }

    int* distance = new int[N];
    int* previous = new int[N];
    bool* visited = new bool[N];

    dijkstra(N, start, roadlength, flow, restrictions, distance, previous, visited);
    vector<int> path = buildPath(start, end, previous);
    if (path.empty()) {
        delete[] distance;
        delete[] previous;
        delete[] visited;
        return paths;
    }
    paths.push_back(path);

    for (int k = 1; k < K; k++) {
        priority_queue<vector<int>, vector<vector<int>>, decltype(&compare)> candidatePaths(&compare);
        for (int m = 0; m < paths.size(); m++) {
            vector<int> currentPath = paths[m];
            for (int i = 0; i < currentPath.size() - 1; i++) {
                int spurNode = currentPath[i];
                int rootPathEnd = currentPath[i + 1];

                int* distanceTmp = new int[N];
                int* previousTmp = new int[N];
                bool* visitedTmp = new bool[N];
                for (int j = 0; j < N; j++) {
                    distanceTmp[j] = distance[j];
                    previousTmp[j] = previous[j];
                    visitedTmp[j] = visited[j];
                }
                visitedTmp[spurNode] = true;

                for (int j = 0; j < i; j++) {
                    visitedTmp[currentPath[j]] = true;
                }

                dijkstra(N, spurNode, roadlength, flow, restrictions, distanceTmp, previousTmp, visitedTmp);

                vector<int> spurPath = buildPath(spurNode, end, previousTmp);
                if (!spurPath.empty()) {
                    vector<int> totalPath = currentPath;
                    totalPath.erase(totalPath.begin() + i + 1, totalPath.end());
                    totalPath.insert(totalPath.end(), spurPath.begin(), spurPath.end());
                    candidatePaths.push(totalPath);
                }
                delete[] distanceTmp;
                delete[] previousTmp;
                delete[] visitedTmp;
            }
        }
        if (candidatePaths.empty()) break;
        vector<int> nextPath = candidatePaths.top();
        candidatePaths.pop();
        bool isDuplicate = false;
        for (const auto& p : paths) {
            if (p == nextPath) {
                isDuplicate = true;
                break;
            }
        }
        if (!isDuplicate) {
            paths.push_back(nextPath);
        }
    }
    delete[] distance;
    delete[] previous;
    delete[] visited;
    return paths;
}